
//二叉树的非递归中序遍历，遍历方式其实和前序遍历一样，打印的地方不一样而已


class Solution1 {
    public List<Integer> inorderTraversal(TreeNode root){
     List<Integer> list=new ArrayList<>();

         if(root==null){
            return list;
        }
      
       TreeNode cur=root;
        Deque<TreeNode> stack=new LinkedList<>();
        while(cur!=null||!stack.isEmpty()){//这个判断比较难想
       while(cur!=null){
           stack.push(cur);
           cur=cur.left;
       }
       TreeNode top=stack.pop();
       //System.out.print(top.val+" ");
       list.add(top.val);
       cur=top.right;

        
    }
   
    
     return list;

    }
}